1. Field of Invention
The present invention relates to a method of encoding a color image to display the color image on a personal computer, a portable terminal, or the like and an encoding device therefor, and a method of decoding the color image and a decoding device therefor.
2. Description of Related Art
Conventionally, when a color image is encoded or decoded, a palette is provided which is formed of a predetermined number of colors. An index is assigned in the palette for each pixel, and the color image is encoded and decoded by encoding and decoding the index.
For example, in a personal computer, game equipment, or the like, an image called a multi-color image is used. The multi-color image is also called a representative color image, a limited color image, or the like. As shown in FIG. 15, these are images for which indexes are assigned to specified colors, that is, colors having specified values of R (red), G (green), and B (blue), and which are expressed by a representative color which is limited to 16 colors, 256 colors, or the like by using the data of the indexes.
In this type of the data of the multi-color image, if each color of R, G, and B is hypothetically expressed by 8 bits (256 groups), a total of 24 bits is needed. However, because the index itself is displayed, for example, by 8 bits, the compression percentage is relatively high. However, the amount of information is still large regardless of the compression. Thus, if the information is processed as-is without any consideration, the required memory capacity becomes large and the communication rate becomes slow so that it is not practical. Therefore, the compression technology is extremely important in the multi-color image as well as in other image data. In particular, the number of colors is limited in the multi-color image so that lossless encoding and decoding, that is, a reversible compression technique is needed.
Recently, the technology of using an entropy encoder and decoder has been focused upon as a method of data compression. One example of the entropy encoding and decoding technology is a technology of arithmetical encoding and decoding. The gist of this technology is disclosed, for example, in Japanese Patent Laid-Open Publication Nos. Sho 62-185413, Sho 63-74324, Sho63-76525, and the like.
FIGS. 20A and 20B show a conventional multi-color image encoding system 50 and decoding system 60 which uses this type of technology. The encoding system 50 includes a line buffer 51 and an entropy encoder 52. The data of the index to be input, that is, the color pixel data 100A, is input to the line buffer 51 and the entropy encoder 52. The color pixel data 100A is input as sequential pixel data in a horizontal scanning order which is raster-scanned as shown in FIG. 21.
Furthermore, as a method for creating the data of the index, that is, the color pixel data 100A, the method to apply the index in order of the color to be input is common. As shown in FIG. 19, phenomena occur such that the colors are significantly different even if the numbers of the index are close (e.g., “1” and “2”) and the colors are close even if the numbers of the index are distant (e.g., “100” and “200”). In order to avoid these phenomena, as shown in Japanese Patent Laid-Open Publication No. Hei 5-328142, there is also a method to apply a sequential number to the approximate color.
The line buffer in the encoding system 50, which functions as a reference pixel formation means, forms the reference pixel data A, B, C, and D for an encoding object pixel X, i.e., that is to be encoded, from the color pixel data 100A which was already input. That is, the line buffer 51 stores the history of a portion that includes n lines (approximately 1-5 lines are commonly used) when scanning the image. Furthermore, every time the color pixel data 100A of the encoding object pixel X is input, a series of pixel data which is formed by the previous pixel A and the surrounding pixels B, C, and D is output to the entropy decoder 52 as reference pixel data 110.
The entropy encoder 52 is formed by using methods such as an arithmetical encoding and Huffman encoding. Furthermore, the reference pixel data 110 is used as a state signal and the object color pixel data 100A is converted and output to the encoding data 200.
Meanwhile, the decoding system 60 is structured so as to include a line buffer 61 and an entropy decoder 62. At this point, the line buffer 61 and the entropy decoder 62 are formed so as to decode and output the encoded data 200 to be input in the completely reverse order of the line buffer 51 and the entropy encoder 52 of the encoding system 50.
Thus, the encoding system 50 and the decoding system 60 use algorithms which are completely opposite to each other and encode the color pixel data 100A to the encoded data 200. Furthermore, it is possible to output the encoded data 200 by decoding the encoded data 200 to the color pixel data 100B. Therefore, the system can be widely used for various uses.
Here, one example of an arithmetical encoding type of the entropy encoder 52 which is used in the system of FIG. 20A is shown in FIG. 22. Moreover, the structure of the entropy decoder 62 of the arithmetical encoding type is substantially the same as the structure of the entropy encoder 52, so the explanation is omitted here.
The entropy encoder 52 is structured so as to include an arithmetical operation part 55 and a generation probability formation means 56 which functions as a state memory device. In the generation probability formation means 56, in order to determine the symbol generation number probability which is needed for encoding, a state parameter table is written. The above-written state parameter is specified by the state signal to be input. Moreover, for the table of the state parameter, which was specified by the state signal, the generation probability operation parameter of the generation probability formation means 56 is output to the arithmetical operation part 55.
Based upon the generation probability which is thus input, the arithmetical operation part 55 performs entropy encoding, and the color pixel data 100A to be input is converted and output as the encoded data 200. Moreover, the generation probability is re-calculated for the state signal by the value of the encoded color pixel data 100A and is input to the generation probability formation means 56 as an operation parameter update value. The update result is stored in the table as the generation probability of the following data so that the compression efficiency of the entropy encoder 52 improves.
Unlike this type of encoding of a multi-color image, a natural image is fetch-encoded by a scanning device and changed to a multi-color image. In a case like this, in order to efficiently encode the color image, various methods and devices are suggested. For example, in Japanese Patent Laid-Open Publication No. Hei 6-178122, the read image is identified in block units as to whether it is a binary area or a multi-value area, and the respective encoded data of binary image, multi-value image (=natural image), and area information is formed.
Furthermore, in Japanese Patent Laid-Open Publication No. Hei 8-9163, the input color image data is divided into blocks of 16×16 pixels, and it is checked whether each block is a color area or a black-and-white area. With respect to a block of a color area, after sampling is performed in a predetermined sub-sampling ratio, DCT conversion, linear quantization, and entropy encoding are performed. Meanwhile, with respect to a block of a black-and-white area, only the Y component of the color components YCrCb which form the color image data is performed by DCT conversion, linear quantization, and entropy encoding.
Moreover, as a method of compression of two-dimensional image data, using the data information of the previous line is also known (see Japanese Patent Laid-Open Publication No. Hei 7-336696). This technology is to output the data of the length and the position of a partial data row on a previous line as data of that partial data row when data of a previous line and the same partial data row which is one pixel exist.
However, in the conventional multi-color image and natural image general encoding and decoding devices, various types of compression technologies are used and the encoded and decoded data amount is significantly reduced, but no solution to this problem has been developed in terms of the data capacity for the palette. That is, in the conventional color image encoding and decoding devices, when the number of colors to be used is increased, the data capacity for the image increases and the refresh rate for the image display tends to be slow. For example, when a color image of 256×256 pixels is encoded or decoded by 256 colors, a memory of 66,304 bytes is needed. That is, when each color needs a total of three bytes in RGB, 256×3 bytes +256×256×1 byte (256 colors)=66,304 bytes is established. Thus, in the case of a screen with the 256×256 pixels, even if 256 colors are used, it requires a large capacity of approximately 70 K bytes and becomes a relatively large amount of data even by using various kinds of complicated compression means. Because of this, when the refresh rate becomes slow, the memory for the display becomes large.
Furthermore, in the prior art as disclosed in Japanese Patent Laid-Open Publication Nos. Hei 6-178122 and Hei 8-9163, because the color image is divided into blocks, since it is divided into black-and-white areas and color areas, and encoded according to these areas, the encoding efficiency improves, but the encoding efficiency does not improve when most of the areas are color areas. In addition, the number of colors to be maintained in order to display the image is the same as the conventional method and a large data capacity of data is required. Moreover, in the compression technology disclosed in Japanese Patent Laid-Open Publication No. Hei 7-336696, the compression efficiency improves when the same pattern continues in the upper and lower directions, but the compression rate does not improve at all when pixels which are different for each line continue in the vertical direction.